package algorithm.recursionAndbacktrack.combination.p401;

import java.util.ArrayList;
import java.util.List;

/**
 * 401. 二进制手表
 */
class Solution_v1 {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> times = new ArrayList<>(); // 统计所有情况
        byte[] hourWeights = {1, 2, 4, 8}; // 小时每个灯亮起代表的权重
        byte[] minuteWeights = {1, 2, 4, 8, 16, 32}; // 分钟每个灯亮起代表的权重
        for (int i = 0; i <= turnedOn && i <= hourWeights.length; i++) {
            if(turnedOn - i > minuteWeights.length) continue;
            readBinaryWatch(i, turnedOn - i, hourWeights, minuteWeights, times);
        }
        return times;
    }

    /**
     *  @param hourTurnedOn 表示小时的灯亮的数量
     * @param minuteTurnedOn 表示分钟的灯亮的数量
     * @param hourWeights 小时每个灯亮起代表的权重
     * @param minuteWeights 分钟每个灯亮起代表的权重
     * @param times 存储所有情况
     */
    private void readBinaryWatch(int hourTurnedOn, int minuteTurnedOn, byte[] hourWeights, byte[] minuteWeights, List<String> times) {
        // 表示小时的灯表示的所有情况
        List<Integer> hours = new ArrayList<>();
        getCombinations(0, hourTurnedOn, hourWeights, hours, 0, 0);

        // 表示分钟的灯表示的所有情况
        List<Integer> minutes = new ArrayList<>();
        getCombinations(0, minuteTurnedOn, minuteWeights, minutes, 0, 0);

        // 将小时和分钟进行组合
        for (int hour : hours) {
            for (int minute : minutes) {
                times.add(hour + ":" + (minute < 10 ? "0" + minute : "" + minute));
            }
        }
    }

    /**
     *
     * @param startIndex 循环开始下标
     * @param turnedOn 灯亮起的数量
     * @param weights 每个灯的权重
     * @param numOfTimes 存储所有情况
     * @param numOfTime 存储一种情况
     * @param count 统计目前遍历到的灯的个数
     */
    private void getCombinations(int startIndex, int turnedOn, byte[] weights, List<Integer> numOfTimes, int numOfTime, int count) {
        if (count == turnedOn) {
            // 如果是小时，必须小于12；如果是分钟，必须小于60
            if ((weights.length == 4 && numOfTime < 12) || (weights.length == 6 && numOfTime < 60)) {
                numOfTimes.add(numOfTime);
            }
            return;
        }
        for (int i = startIndex; i < weights.length - (turnedOn - count) + 1; i++) {
            getCombinations(i + 1, turnedOn, weights, numOfTimes, numOfTime + weights[i], count + 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution_v1().readBinaryWatch(8));
    }
}